package main.leetcode.clockin.April;

import java.util.ArrayList;
import java.util.List;

/**
 * 22.括号生成
 *
 * <p>数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * <p>
 *
 * <p>示例： 输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day9 {
    public static void main(String[] args) {
        System.out.println(new day9().generateParenthesis(3));
    }
    //    public List<String> generateParenthesis(int n) {
    //        List<String> list = new ArrayList<>();
    //        if (n == 0) {
    //            list.add("");
    //        } else {
    //            for (int i = 0; i < n; ++i) {
    //                for (String left : generateParenthesis(i)) {
    //                    for (String right : generateParenthesis(n - 1 - i)) {
    //                        list.add("(" + left + ")" + right);
    //                    }
    //                }
    //            }
    //        }
    //        return list;
    //    }

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        backTrack(list, 0, 0, n, "");
        return list;
    }

    private void backTrack(List<String> list, int left, int right, int n, String cur) {
        if (cur.length() == n * 2) {
            list.add(cur);
            return;
        }
        if (left < n) backTrack(list, left + 1, right, n, cur + "(");
        if (right < left) backTrack(list, left, right + 1, n, cur + ")");
    }
}
